home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-03 / iqb9109.zip / QSORT.BAS < prev    next >
BASIC Source File  |  1991-09-09  |  3KB  |  90 lines
  1. ' QSort.Bas
  2. ' QuickSort subprogram and RandInt% function extracted from the
  3. ' Microsoft-supplied program SORTDEMO.BAS.
  4. ' Portions Copyright by Microsoft Corporation.
  5. '
  6.  
  7. ' $INCLUDE: 'QSORT.BI'
  8.  
  9. ' ============================== QuickSort ===================================
  10. '   QuickSort works by picking a random "pivot" element in SortArray, then
  11. '   moving every element that is bigger to one side of the pivot, and every
  12. '   element that is smaller to the other side.  QuickSort is then called
  13. '   recursively with the two subdivisions created by the pivot.  Once the
  14. '   number of elements in a subdivision reaches two, the recursive calls end
  15. '   and the array is sorted.
  16. ' ============================================================================
  17. '
  18. SUB QuickSort (Low AS INTEGER, High AS INTEGER)
  19. DIM RandIndex AS INTEGER
  20. DIM I AS INTEGER, J AS INTEGER
  21. DIM Partition AS SortType
  22.  
  23.    IF Low < High THEN
  24.  
  25.       ' Only two elements in this subdivision; swap them if they are out of
  26.       ' order, then end recursive calls:
  27.  
  28.       IF High - Low = 1 THEN
  29.  
  30.          ' Here's where the recursion terminates. If the two elements
  31.          ' of this subdivision are out of order, swap them.
  32.  
  33.          IF SortArray(Low).SortKey > SortArray(High).SortKey THEN
  34.             SWAP SortArray(Low), SortArray(High)
  35.          END IF
  36.       ELSE
  37.  
  38.          ' Pick a pivot element at random, then move it to the end:
  39.  
  40.          RandIndex = RandInt%(Low, High)
  41.          SWAP SortArray(High), SortArray(RandIndex)
  42.          Partition.SortKey = SortArray(High).SortKey
  43.          DO
  44.  
  45.             ' Move in from both sides towards the pivot element:
  46.  
  47.             I = Low: J = High
  48.             DO WHILE (I < J) AND (SortArray(I).SortKey <= Partition.SortKey)
  49.                I = I + 1
  50.             LOOP
  51.             DO WHILE (J > I) AND (SortArray(J).SortKey >= Partition.SortKey)
  52.                J = J - 1
  53.             LOOP
  54.  
  55.             ' If we haven't reached the pivot element, it means that two
  56.             ' elements on either side are out of order, so swap them:
  57.  
  58.             IF I < J THEN
  59.                SWAP SortArray(I), SortArray(J)
  60.             END IF
  61.          LOOP WHILE I < J
  62.  
  63.          ' Move the pivot element back to its proper place in the array:
  64.  
  65.          SWAP SortArray(I), SortArray(High)
  66.  
  67.          ' Recursively call the QuickSort procedure (pass the smaller
  68.          ' subdivision first to use less stack space):
  69.  
  70.          IF (I - Low) < (High - I) THEN
  71.             QuickSort Low, I - 1
  72.             QuickSort I + 1, High
  73.          ELSE
  74.             QuickSort I + 1, High
  75.             QuickSort Low, I - 1
  76.          END IF
  77.       END IF
  78.    END IF
  79. END SUB
  80.  
  81. ' =============================== RandInt% ===================================
  82. '   Returns a random integer greater than or equal to the Lower parameter
  83. '   and less than or equal to the Upper parameter.
  84. ' ============================================================================
  85. '
  86. FUNCTION RandInt% (Lower AS INTEGER, Upper AS INTEGER) STATIC
  87.    RandInt% = INT(RND * (Upper - Lower + 1)) + Lower
  88. END FUNCTION
  89.  
  90.